Năm 938, Dương Đình Nghệ bị Kiều Công Tiễn sát hại. Phạm Lệnh Công theo Ngô Quyền kéo quân ra thành Đại La tiêu diệt kẻ phản bội.[cần dẫn nguồn] Do lo sợ bị tiêu diệt, Kiều Công Tiễn đã cầu cứu nhà Nam Hán. Vua Nam Hán lúc bấy giờ là Lưu Cung cho con trai là Hoằng Thao kéo quân theo đường thủy sang giúp (thực chất là nhân cơ hội chiếm lấy Giao Châu). Đầu mùa đông năm 938, cùng với Ngô Quyền dẹp xong bọn phản loạn Kiều Công Tiễn và chuẩn bị toàn lực để đối phó với sự xâm lăng của quân Nam Hán.

Theo lệnh của Ngô Quyền, Phạm Lệnh Công cùng với quân sĩ đóng cọc có bịt sắt nhọn xuống lòng sông Bạch Đằng và nhử quân địch vào khu vực này khi thủy triều lên.[cần dẫn nguồn] Quân giặc thấy quân của Ngô Quyền chỉ có thuyền nhẹ, quân ít tưởng có thể dễ thắng lên hùng hổ tiến vào. Đợi đến khi thủy triều xuống mới hạ lệnh cho quân sĩ đổ ra đánh. Thuyền chiến lớn của quân Nam Hán bị mắc cạn và lần lượt bị cọc đâm thủng gần hết. Quân Nam Hán thua chạy, còn Hoằng Thao bỏ mạng cùng với quá nửa quân sĩ. Từ đó nhà Nam Hán bỏ hẳn mộng xâm lược.

Phạm Lệnh Công được Ngô Quyền trọng dụng và phong cho đến chức Đông Giáp tướng quân (tức là ông tướng cai quản vùng xứ Đông).[cần dẫn nguồn]